// 给定两个链表的头节点，如何找出它们相交的起始节点

// 思路1：两个链表如果相交的话，必然从某个节点开始相等，可以计算链表长度，然后从相同剩余长度节点开始比较
// 时间复杂度：O(m+n)，m是链表A的节点数，n是链表B的节点数
// 空间复杂度：O(1)

const { LinkedList, ListNode} = require('./64.设计链表')

function getIntersectionNode(head1, head2) {
    if (!head1 || !head2) {
        return null
    }
    let len1 = getLength(head1)
    let len2 = getLength(head2)
    if (len1 < len2) {
        [len1, len2] = [len2, len1];
        [head1, head2] = [head2, head1];
    }
    let i = len1 - len2
    while (i) {
        head1 = head1.next
        i--
    }
    // 此时两个head剩余节点数相同
    while (head1 && head2 && head1 !== head2) {
        head1 = head1.next
        head2 = head2.next
    }
    return head1
}

function getLength(head) {
    let count = 0
    let cur = head
    while (cur) {
        count++
        cur = cur.next
    }
    return count
}


// 思路2，数学公式可以证明，当head1遍历到空时指向head2的头节点，当head2遍历到空指向head1的头节点，最终将在相交点汇合，或者两者都为null
// 时间复杂度：O(m+n)，m是链表A的节点数，n是链表B的节点数
// 空间复杂度：O(1)

function getIntersectionNode2(head1, head2) {
    if (!head1 || !head2) {
        return null
    }
    let cur1 = head1
    let cur2 = head2
    while (cur1 !== cur2) {
        cur1 = !cur1 ? head2 : cur1.next
        cur2 = !cur2 ? head1 : cur2.next
    }
    return cur1
}

let node1 = new ListNode(2)
let node2 = new ListNode(5)
let node3 = new ListNode(1)
let node4 = new ListNode(7)
node1.next = node2
node2.next = node3
node3.next = node4

let node11 = new ListNode(22)
let node22 = new ListNode(55)
let node33 = new ListNode(11)
let node44 = new ListNode(77)
node11.next = node22
node22.next = node33
node33.next = node44
node44.next = node4

console.log(getIntersectionNode(node1, node11))
console.log(getIntersectionNode2(node1, node11))